/**
 * @param {number[]} arr
 * @return {number}
 */
export var lenLongestFibSubseq = function (arr) {
  const n = arr.length
  // 记录每个数字对应的下标
  const valMap = new Map()
  for (let i = 0; i < n; ++i) valMap.set(arr[i], i)
  // dp[i][j] 代表i和j昨为最后两个数时的最长子序列长度
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0))
  let ans = 0
  for (let i = 0; i < n; i++) {
    for (let j = n - 1; j >= 0; j--) {
      if (arr[j] * 2 <= arr[i]) break
      const kValue = arr[i] - arr[j]
      if (valMap.has(kValue)) {
        const k = valMap.get(kValue)
        dp[i][j] = Math.max(dp[j][k] + 1, 3)
        ans = Math.max(ans, dp[i][j])
      }
    }
  }
  return ans
}
